/*
练习11-2 是否二叉查找树
分数 25
作者 陈越
单位 浙江大学

本题要求实现函数，判断给定二叉树是否二叉查找树。
函数接口定义：

bool IsBST(BinaryTree tree);

其中 BinaryTree 结构定义如下：

typedef int TElemSet; // 树结点元素为整型 
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;      // 数据元素 
    BinaryTree left;    // 左孩子指针 
    BinaryTree right;   // 右孩子指针 
};

函数 IsBST 须判断给定的 tree 是否二叉查找树，如果是则返回 true，否则返回 false。
注意：题目保证所有键值均为正整数。
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int TElemSet; /* 树结点元素为整型 */
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;      /* 数据元素 */
    BinaryTree left;    /* 左孩子指针 */
    BinaryTree right;   /* 右孩子指针 */
};

BinaryTree BuildTree(); /* 由裁判实现，细节不表 */
bool IsBST(BinaryTree tree);

int main(void)
{
    BinaryTree T;
    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

bool IsBSTUtil(BinaryTree tree, TElemSet min, TElemSet max) {
    if (tree == NULL) {
        return true;
    }
    if (tree->data <= min || tree->data >= max) {
        return false;
    }
    return IsBSTUtil(tree->left, min, tree->data) && IsBSTUtil(tree->right, tree->data, max);
}

bool IsBST(BinaryTree tree) {
    return IsBSTUtil(tree, 0, 0xffffff);
}